# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=11
    
    In the 20×20 grid below, four numbers along a diagonal line have been
    marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

    The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

    What is the greatest product of four adjacent numbers in any direction
    (up, down, left, right, or diagonally) in the 20×20 grid?
    
    PERFORMANCE
    time <function solution at 0x7fd9235567d0>: 0.003742 s
"""
#
# Import
#
import time


#
# Globals / Constants
#
RAW_GRID = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
"""

def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected):
    assert value == expected, "value %s != expected %s" % (
        value, expected)


#
# Test Case / Solution
#
@timeit    
def test_case():
    grid = parse_grid(RAW_GRID)
    
    assert_match(len(grid), 20)
    assert_match(len(grid[0]), 20)
    assert_match(type(grid[0][0]), int)
    assert_match(grid[0][0], 8)
    
    test_grid = """
01 02 09
04 08 06
07 05 03
"""
    grid = parse_grid(test_grid)
    assert_match(grid[0], [1, 2, 9])
    
    x, y = 0, 0
    right_seq = right(grid, 3, x, y)
    down_seq = down(grid, 3, x, y)
    down_right_seq = down_right(grid, 3, x, y)
    assert_match(right_seq, [1, 2, 9])
    assert_match(down_seq, [1, 4, 7])
    assert_match(down_right_seq, [1, 8, 3])
    assert_match(down(grid, 2, 2, 2), [0])
    
    product = max_grid_product(grid, 3)
    assert_match(product, 7*8*9)
    
    #print grid
    print "test case passed!"

@timeit
def solution():
    return max_grid_product(parse_grid(RAW_GRID), 4)

#
# Support Code
#
def max_grid_product(grid, seq_len):
    max_product = 0
    num_cols = len(grid)
    num_rows = len(grid[0])
    
    for y in range(num_cols):
        for x in range(num_rows):
            right_prod = multiply(right(grid, seq_len, x, y))
            down_prod = multiply(down(grid, seq_len, x, y))
            up_diag_prod = multiply(up_right(grid, seq_len, x, y))
            down_diag_prod = multiply(down_right(grid, seq_len, x, y))

            max_product = max([max_product, right_prod, down_prod,
                up_diag_prod, down_diag_prod])
            
    return max_product

def multiply(seq):
    prod = 1
    for n in seq:
        prod *= n
    return prod

def right(grid, seq_len, x, y):
    try:
        return [v for v in grid[y][x:x+seq_len]]
    except IndexError:
        return [0]
                
def down(grid, seq_len, x, y):
    seq = []
    try:
        for y in range(y, y+seq_len):
            seq.append(grid[y][x])
        return seq
    except IndexError:
        return [0]
        
def up_right(grid, seq_len, x, y):
    seq = []
    try:
        for n in range(seq_len):
            seq.append(grid[y-n][x+n])
        return seq        
    except IndexError:
        return [0]
        
def down_right(grid, seq_len, x, y):
    seq = []
    try:
        for n in range(seq_len):
            seq.append(grid[y+n][x+n])
        return seq        
    except IndexError:
        return [0]

def parse_grid(grid_str):
    grid = []
    rows = [row.strip() for row in grid_str.split('\n') if row.strip() != ""]
    
    for row in rows:
        cols = row.split(' ')
        row_cols = [int(col.strip()) for col in cols if col.strip() != ""]
        grid.append(row_cols)
        
    return grid    
    


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    